package tree.structure.treetype;

/**
 * @user 26233
 * @create 2020-04-04 23:08:00
 * @description 红黑树实现
 *
 *
 *
 **/

/*

红黑树的特性会导致有些情况不会出现

 */

public class RedBlackTree {

    TreeNodeComparable<Integer> root;

    public void insert(Integer data){
        TreeNodeComparable newNode = new TreeNodeComparable(data);
        TreeNodeComparable tempRoot = root;
        if (root == null){
            root = newNode;
            root.nodeColor = 1;// 根节点为黑色
        }else{
            while(tempRoot != null){
                if (data.compareTo((Integer)tempRoot.getValue()) > 0){
                    // data 大
                    if(tempRoot.right == null){
                        tempRoot.right = newNode;
                        newNode.parent = tempRoot;
                        rightInsertBalance(newNode);
                        break;
                    }
                    tempRoot = (TreeNodeComparable) tempRoot.right;
                }else{
                    if(tempRoot.left == null){
                        tempRoot.left = newNode;
                        newNode.parent = tempRoot;
                        leftInsertBalance(newNode);
                        break;
                    }
                    tempRoot = (TreeNodeComparable) tempRoot.left;
                }
            }
        }
    }

    // 检查父节点是不是red
    public void leftInsertBalance(TreeNodeComparable currentNode){

        while(currentNode.parent != null){
            if(currentNode.parent.left == currentNode){
                if (((TreeNodeComparable)currentNode.parent).nodeColor == 1){
                    return;
                }else{
                    // 链式R-R
                    TreeNodeComparable tempParent = (TreeNodeComparable) currentNode.parent.parent;
                    TreeNodeComparable tempNode = (TreeNodeComparable) currentNode.parent.parent.parent;
                    if(tempNode == null){

                        currentNode.nodeColor = 1;
                        tempParent.nodeColor = 1;
                        ((TreeNodeComparable) currentNode.parent).nodeColor = 1;

                        tempParent.left = currentNode.parent.right;
                        if (currentNode.parent.right != null) currentNode.parent.right.parent = tempParent;
                        currentNode.parent.right = tempParent;
                        currentNode.parent.parent = null;
                        tempParent.parent = currentNode.parent;
                        root = (TreeNodeComparable<Integer>) currentNode.parent;
                        return;
                    }else{

                        currentNode.nodeColor = 1;
                        tempParent.nodeColor = 1;
                        ((TreeNodeComparable) currentNode.parent).nodeColor = 0;

                        tempParent.left = currentNode.parent.right;
                        if (currentNode.parent.right != null) currentNode.parent.right.parent = tempParent;
                        currentNode.parent.right = tempParent;
                        tempParent.parent = currentNode.parent;
                        if (tempNode.left == tempParent){
                            tempNode.left = currentNode.parent;
                        }else{
                            tempNode.right = currentNode.parent;
                        }

                        currentNode.parent.parent = tempNode;
                        currentNode = (TreeNodeComparable) currentNode.parent;
                    }
                }
            }else{
                // 递归上去的
                if (currentNode.parent.left != null){
                    if(((TreeNodeComparable)currentNode.parent.left).nodeColor == 0){
                        // 平行R-R
                        ((TreeNodeComparable)currentNode.parent.left).nodeColor = 1;
                        currentNode.nodeColor = 1;
                        ((TreeNodeComparable)currentNode.parent).nodeColor = 1;
                        currentNode = (TreeNodeComparable) currentNode.parent;
                    }else{
                        // 左旋
                        TreeNodeComparable tempParent = (TreeNodeComparable) currentNode.parent;
                        TreeNodeComparable tempNode = (TreeNodeComparable) currentNode.parent.parent;

                        currentNode.nodeColor = 1;
                        tempParent.nodeColor = 0;

                        tempParent.right = currentNode.left;
                        if (currentNode.left != null) currentNode.left.parent = tempParent;
                        currentNode.left = tempParent;

                        tempParent.parent = currentNode;

                        if (tempNode == null){
                            root = currentNode;
                            currentNode.parent = null;
                            return;
                        }else{
                            if (tempNode.left == tempParent) tempNode.left = currentNode;
                            else tempNode.right = currentNode;
                        }
                    }
                }
            }
        }
    }

    public void rightInsertBalance(TreeNodeComparable currentNode){
        if(currentNode.parent.left == null){
            Object tempData = currentNode.parent.getValue();
            currentNode.parent.setValue(currentNode.getValue());
            currentNode.setValue(tempData);
            currentNode.parent.left = currentNode;
            currentNode.parent.right = null;
        }else{
            // B-R
            if (((TreeNodeComparable)currentNode.parent.left).nodeColor == 1){
                currentNode.nodeColor = 1;
                ((TreeNodeComparable) currentNode.parent.left).nodeColor = 0;
                leftInsertBalance((TreeNodeComparable) currentNode.parent.left);
            }else{
                while(currentNode.parent != null){
                    // 向上递归的时候的平行R-R
                    if (((TreeNodeComparable) currentNode.parent.left).nodeColor == 0){
                        currentNode.nodeColor = 1;
                        ((TreeNodeComparable) currentNode.parent.left).nodeColor = 1;
                        ((TreeNodeComparable)currentNode.parent).nodeColor = 0;
                        currentNode = (TreeNodeComparable) currentNode.parent;
                    }else{// 向上递归的时候的B-R
                        currentNode.parent.right = currentNode.left;
                        currentNode.left = currentNode.parent;

                        currentNode.nodeColor = ((TreeNodeComparable) currentNode.parent).nodeColor;

                        if (currentNode.left.parent != null){
                            if (currentNode.left.parent.left == currentNode.left){
                                currentNode.left.parent.left = currentNode;
                            }else{
                                currentNode.left.parent.right = currentNode;
                            }
                            currentNode.parent = currentNode.left.parent;
                        }else{
                            currentNode.parent = null;
                            root = currentNode;
                            return;
                        }
                        currentNode.left.parent = currentNode;
                        ((TreeNodeComparable)currentNode.left).nodeColor = 0;
                        currentNode = (TreeNodeComparable) currentNode.left;// 可能存在链式 R-R
                        leftInsertBalance(currentNode);
                        return;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        // int[] data = new int[]{6, 7, 4, 5, 10, 12, 13, 14};

        // 测试数据
        int[] data = new int[]{50, 25, 15, 40, 20, 30, 100, 35, 38, 31};
        // int[] data = new int[]{15, 20, 25, 30, 31, 35, 38, 40, 50, 100};

        RedBlackTree redBlackTree = new RedBlackTree();

        // 验证
        for (int i = 0; i < data.length; i++) {
            redBlackTree.insert(data[i]);
        }

        System.out.println("redBlackTree = " + redBlackTree);
    }

}
